/**
 * 
 */
package net.sf.graph4j.algorithm.graph.maxflow;

import net.sf.graph4j.element.graph.Edge;
import net.sf.graph4j.element.graph.Graph;
import net.sf.graph4j.element.graph.Vertex;
import net.sf.graph4j.utils.Utils;

/**
 * @author palomino
 *
 */
public abstract class AbstractPushRelabelMaxFlow implements IMaximumFlow {

	protected FlowDescriptor flow;
	protected Vertex source;
	protected Vertex sink;
	protected Graph g;

	/**
	 * 
	 */
	public AbstractPushRelabelMaxFlow() {
		super();
		// TODO Auto-generated constructor stub
	}

	protected void reLabel(Vertex v) {
		// TODO Auto-generated method stub
		int min = Integer.MAX_VALUE;
		for (Vertex u : v.getConnectingEdgesToVertices().values()) {
			if (flow.getResidualGraph().containsEdge(flow.map(v), flow.map(u)))
				if ((Integer)u.getProperty(PropertyFlowHeight) < min)
					min = (Integer)u.getProperty(PropertyFlowHeight);
		}
		v.putProperty(PropertyFlowHeight, min + 1);
		
		flow.refreshResidualGraph();
	}

	protected boolean canRelabel(Vertex v) {
		// TODO Auto-generated method stub
		for (Vertex u : v.getConnectingEdgesToVertices().values()) {
			if (flow.getResidualGraph().containsEdge(flow.map(v), flow.map(u)))
				if ((Integer)v.getProperty(PropertyFlowHeight) > (Integer)u.getProperty(PropertyFlowHeight))
					return false;
		}
		
		return isOverFlow(v);
	}

	protected void reversePush(Edge e) {
		// TODO Auto-generated method stub
		double d = Math.min((Double)e.getTarget().getProperty(PropertyExcessFlow), flow.getTransResidualEdge(e).getWeight());
		
		Utils.increase(e, PropertyFlow, -d);
		Utils.increase(e.getSource(), PropertyExcessFlow, d);
		Utils.increase(e.getTarget(), PropertyExcessFlow, -d);
		
		flow.refreshResidualGraph();
	}

	protected boolean canReversePush(Edge e) {
		// TODO Auto-generated method stub
		return isOverFlow(e.getTarget())
			&& flow.getTransResidualEdge(e) != null
			&& (Integer)e.getTarget().getProperty(PropertyFlowHeight) == 
				(Integer)e.getSource().getProperty(PropertyFlowHeight) + 1;
	}

	protected void push(Edge e) {
		// TODO Auto-generated method stub
		
		double d = Math.min((Double)e.getSource().getProperty(PropertyExcessFlow), flow.getCisResidualEdge(e).getWeight());
		
		Utils.increase(e, PropertyFlow, d);
		Utils.increase(e.getSource(), PropertyExcessFlow, -d);
		Utils.increase(e.getTarget(), PropertyExcessFlow, d);
		
		flow.refreshResidualGraph();
	}
	
	protected void push(Vertex source, Vertex target) {
		// TODO Auto-generated method stub
		Edge cisEdge = g.getEdgeByVertex(source, target);
		Edge transEdge = g.getEdgeByVertex(target, source);
		
		if (cisEdge != null && flow.getCisResidualEdge(cisEdge) != null)
			push (g.getEdgeByVertex(source, target));
		else if (transEdge != null && flow.getTransResidualEdge(transEdge) != null)
			reversePush(g.getEdgeByVertex(target, source));
	}

	protected boolean canPush(Edge e) {
		// TODO Auto-generated method stub
		return isOverFlow(e.getSource())
			&& flow.getCisResidualEdge(e) != null
			&& (Integer)e.getSource().getProperty(PropertyFlowHeight) == 
				(Integer)e.getTarget().getProperty(PropertyFlowHeight) + 1;
	}

	/**
	 * @return Returns the flow.
	 */
	public FlowDescriptor getFlow() {
		return flow;
	}

	protected boolean isOverFlow(Vertex v) {
		if (v == sink || v == source)
			return false;
		return (Double)v.getProperty(PropertyExcessFlow) > 0.0;
	}

	protected void initPreFlow(Graph g, Vertex source) {
		for (Vertex v : g.getVertices()) {
			v.putProperty(PropertyFlowHeight, 0);
			v.putProperty(PropertyExcessFlow, 0.0);
		}
		
		flow = new FlowDescriptor(g);
		
		source.putProperty(PropertyFlowHeight, g.getVertices().size());
		
		for (Edge e : source.getOutgoingEdgesToVertices().keySet()){
			double capacity = flow.getCisResidualEdge(e).getWeight();
			e.putProperty(PropertyFlow, capacity);
			e.getTarget().putProperty(PropertyExcessFlow, capacity);
			Utils.increase (source, PropertyExcessFlow, - capacity);
		}
	}

}
